00100	                              CHAPTER I
00200	
00300	                      INTRODUCTION TO LISP 1.5
00400	
00500	1. Lists.
00600	
00700		Symbolic information in LISP is  expressed  by  S-expressions
00800	and  these  are  represented  in  the  memory of the computer by list
00900	structures. Before giving formal  definitions,  we  shall  give  some
01000	examples.
01100	
01200		The most common form of S-expression is the  list,  and  here
01300	are some lists:
01400	
01500	The list
01600		(A B C E)
01700	has four elements.
01800	
01900	The list
02000		(A B (C D) E)
02100	has four elements one of which is itself a list.
02200	
02300	The list
02400		(A)
02500	has one element.
02600	
02700	The list
02800		((A B C D))
02900	also has one element which itself is a list.
03000	
03100	The list
03200		()
03300	has no elements; it is also written
03400		NIL.
03500	The list
03600		(PLUS X Y)
03700	has three elements and may be used to represent the expression
03800		x+y.
03900	
04000	The list
04100		(PLUS (TIMES X Y) X 3)
04200	has four elements and may be used to represent the expression
04300		xy+x+3.
04400	
04500	The list
04600	(EXIST X (ALL Y (IMPLIES (P X) (P Y))))
04700	may be used to represent the logical expression
04800		(∃x)(∀y).P(x)⊃P(y).
04900	
05000	The list
05100		(INTEGRAL 0 ∞ (TIMES (EXP (TIMES I X Y)) (F X) X))
05200	may be used to represent the expression
05300	
05400		  e   f(x)dx.
05500	
05600	The list
05700		((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E))
05800	is used to represent the network of Figure 1 according  to  a  scheme
05900	whereby  there  is a sublist for each vertex consisting of the vertex
06000	itself followed by the vertices to which it is connected.
06100	
06200	
06300	
06400	
06500	
06600	
06700	
06800	
06900	
07000	
07100	                              Figure 1

07200	
07300		The  elements  of  a  list  are surrounded by parentheses and
07400	separated by spaces.  A list may have any number of terms and any  of
07500	these  terms  may  themselves  be  lists.   In  this case, the spaces
07600	surrounding a sublist  may  be  omitted,  and  extra  spaces  between
07700	elements of a list are allowed.  Thus the lists
07800		(A B(C  D)    E)
07900	and
08000		(A B (C D) E)
08100	are regarded as the same.
08200	
08300	2. Atoms.
08400	
08500		The expressions A, B, X, Y, 3, PLUS, and ALL occurring in the
08600	above  lists are called atoms.  In general, an atom is expressed by a
08700	sequence of capital letters,  digits,  and  special  characters  with
08800	certain  exclusions.   The exclusions are <space>, <carriage return>,
08900	and the other non-printing  characters,  and  also  the  parentheses,
09000	brackets,  semi-colon,  and  comma.   Numbers are expressed as signed
09100	decimal or octal numbers,  the  exact  convention  depending  on  the
09200	implementation.  Floating  point  numbers  are  written  with decimal
09300	points and, when appropriate, an exponent notation depending  on  the
09400	implementation.   The  reader  should consult the programmer's manual
09500	for the LISP implementation he intends to use.
09600	
09700		Some examples of atoms are
09800		THE-LAST-TRUMP
09900		A307B
10000		345
10100		3.14159,
10200	and from these we can form lists like
10300		((345 3.14159 -47) A307B THE-LAST-TRUMP -45.21).
10400	
10500	3. List structures.
10600	
10700		Lists  are  represented in the memory of the computer by list
10800	structures.    A list structure is a collection of memory words  each
10900	of  which  is  divided  into  two  parts, and each part is capable of
11000	containing an address in memory. The two parts are called are  called
11100	the  a-part  and  the  d-part.  There  is  one computer word for each
11200	element of the list, and the a-part of the word contains the  address
11300	of the list or atom representing the element, and the d-part contains
11400	the address of the word representing the next element  of  the  list.
11500	If the list element is itself a list, then, of course, the address of
11600	the first word of its list structure is given in the  a-part  of  the
11700	word  representing  that  element.  A diagram shows this more clearly
11800	than words, and the list structure corresponding to the  list  %(PLUS
11900	(TIMES  X  Y)  X  3)%  which may represent the expression %xy+x+3% is
12000	shown in figure 2.
12100	
12200	
12300	
12400	
12500	
12600	
12700	
12800	
12900	
13000	
13100	
13200	                              Figure 2.
13300	
13400		Atoms  are  represented  by  the  addresses of their property
13500	lists which are list structures of a special kind  depending  on  the
13600	implementation.   (In  some  implementations,  the  first  word  of a
13700	property list is in a special are of memory, in others the first word
13800	is  distinguished  by  sign, in still others it has a special a-part.
13900	For basic LISP programming, it is  enough  to  know  that  atoms  are
14000	distinguishable  from  other  list  structures  by a predicate called
14100	%at.)
14200	
14300		The  last  word  of  a list cannot have the address of a next
14400	word in its d-part since there isn't any next word,  so  it  has  the
14500	address of a special atom called %NIL.
14600	
14700		A  list  is  referred  to  by giving the address of its first
14800	element.  According to this convention, we see that the a-part  of  a
14900	list  word  is  the  list  element  and  the d-part is a pointer to a
15000	sublist formed by deleting the first element.  Thus the first word of
15100	the  list  structure  of  figure  2  contains  a  pointer to the list
15200	structure representing the atom %PLUS, while its d-part points to the
15300	list %((TIMES X Y) X 3).  The second word contains the list structure
15400	representing %(TIMES X Y)% in  its  a-part  and  the  list  structure
15500	representing %(X 3)% in its d-part.  The last word points to the atom
15600	%3% in its a-part and has a pointer to the atom %NIL% in its  d-part.
15700	This is consistent with the convention that %NIL% represents the null
15800	list.
15900	
16000	4. S-expressions.
16100	
16200		When we examine the way list structures  represent  lists  we
16300	see  a  curious  asymmetry.   Namely,  the  a-part of a list word can
16400	contain an atom or a list, but the d-part can contain only a list  or
16500	the special atom %NIL.   This restriction is quite unnatural from the
16600	computing point of view,  and  we  shall  allow  arbitrary  atoms  to
16700	inhabit  the  d-parts  of  words, but then we must generalize the way
16800	list structures are expressed as character strings. To  do  this,  we
16900	introduce the notion of S-expression.
17000	
17100		An  S-expression is either an atom or a pair of S-expressions
17200	separated by " . " and surrounded by parentheses.   In  BNF,  we  can
17300	write
17400	
17500	<S-expression> ::= <atom>|(<S-expression> . <S-expression>).
17600	
17700	Examples of S-expressions are
17800	
17900		A
18000		(A . B)
18100		(A . (B . A))
18200		(PLUS (X . (Y . NIL)))
18300		(3 . 3.4).
18400	
18500	The spaces around the . may be  omitted  when  this  will  not  cause
18600	confusion.   The only possible confusion is of the dot separator with
18700	a decimal point in numbers.  Thus, in the above cases, we  may  write
18800	(A.B),  (A.(B.A)),  and  (PLUS.(X.(Y.NIL))),  but if we wrote (3.3.4)
18900	confusion would result.
19000	
19100		In the memory of a computer, an S-expression  is  represented
19200	by  the  address of a word whose a-part contains the first element of
19300	the pair and whose d-part contains the second element  of  the  pair.
19400	Thus,  the S-expressions %(A.B), %(A.(B.A)), and %(PLUS.(X.(Y.NIL)))%
19500	are represented by the list structures of figure 3.
19600	
19700	
19800	
19900	
20000	
20100	
20200	
20300	
20400	
20500	
20600	
20700	
20800	
20900	
21000	
21100	                              Figure 3.
21200	
21300		Note   that   the  list  %(PLUS%X%Y)%  and  the  S-expression
21400	%(PLUS.(X.(Y.NIL)))% are represented  in  memory  by  the  same  list
21500	structure.  The simplest way to treat this is to regard S-expressions
21600	as primary and lists  as  abbreviations  for  certain  S-expressions,
21700	namely those that never have any atom but %NIL% as the second part of
21800	a pair. In giving  input  to  LISP,  either  the  list  form  or  the
21900	S-expression  form may be used for lists.  On output, LISP will print
22000	a list structure as a  list  as  far  as  it  can,  otherwise  as  an
22100	S-expression.  Thus,  some list structures will be printed in a mixed
22200	notation, e.g. ((A.B) (C.D) (3)).
22300	
22400		In general, the list %(a%b%...%z)%  may  be  regarded  as  an
22500	abbreviation of the S-expression (a.(b.(c.( ... (z.NIL) ... ))).
22600	
22700	                              Exercises
22800	
22900		1. If we represent sums and products as indicated  above  and
23000	use %(MINUS%X), %(QUOTIENT%X%Y), and %(POWER%X%Y)% as representations
23100	of %-x, %x/y, and %x↑y% respectively, then
23200		a. What do the lists  
23300		(QUOTIENT 2 (POWER (PLUS X (MINUS Y)) 3))
23400	and
23500		(PLUS -2 (MINUS 2) (TIMES X (POWER Y 3.3)))
23600	represent?
23700		b.    How    are    the   expressions   xyz+3(u+v)↑(-3)   and
23800	(xy-yx)/(xy+yx) to be represented?
23900	
24000		2. In the above  mentioned  graph  notation,  what  graph  is
24100	represented by the list
24200	
24300		((A D E F)(B D E F)(C D E F)(D A B C)(E A B C)(F A B C))?
24400	
24500		3. Write the list ((PLUS (TIMES X Y) X 3) as an S-expression.
24600	This is sometimes referred to as "dot-notation".
24700	
24800		4.  Write  the  following  S-expressions  in list notation to
24900	whatever extent is possible:
25000		a. (A.NIL)
25100		b. (A.B)
25200		c. ((A.NIL).B)
25300		d. ((A.B).((C.D).NIL).
25400	
25500	5. The basic functions and predicates of LISP.
25600	
25700		Just as numerical computer programs are  based  on  the  four
25800	arithmetic  operations  of  addition subtraction, multiplication, and
25900	division, and the arthmetic predicates of equality and comparison, so
26000	symbolic  computation  has  its basic predicates and functions.  LISP
26100	has three basic functions and two predicates.
26200	
26300		First,  we  have two functions %a% and %d.  a%x is the a-part
26400	of the S-expression %x.  Thus, %a(A.B)%=%A, and  %a((A.B).A)%=%(A.B).
26500	%d%x%  is  the  d-part  of the S-expression %x. Thus %d(A.B)%=%B, and
26600	%d((A.B).A)%=%B. %a%x% and %d%x% are undefined in basic LISP when %x%
26700	is an atom, but they may have a meaning in some implementations.
26800	
26900		Since  lists  are  a  particular  kind  of  S-expression, the
27000	meanings of %a% and %d% for lists are also determined  by  the  above
27100	definitions.  Thus, we have
27200	
27300		a(A B C D) = A
27400	
27500	and
27600	
27700		d(A B C D) = (B C D),
27800	
27900	and we see that, in general, %a%x% is the first element of  the  list
28000	%x, and %d%x% is the rest of the list, deleting that first element.
28100	
28200		Notice  that  for S-expressions, the definitions of %a%x% and
28300	%d%x% are symmetrical, while for lists the symmetry is lost.  This is
28400	because  of  the  unsymmetrical nature of the convention that defines
28500	lists in terms of S-expressions.
28600	
28700		Notice, further,  our  convention  of  writing  %a%  and  %d%
28800	without  brackets  surrounding the argument.  Also, we use lower case
28900	letters for our function names and for variables, reserving the upper
29000	case letters for the S-expressions themselves.
29100	
29200		The  third  function %cons[x,y]% forms the S-expression whose
29300	a-part and d-part are %x% and %y% respectively.  Thus
29400	
29500		cons[(A.B),A] = ((A.B).A).
29600	
29700		We  see  that  for  lists,  %cons%  is a prefixing operation.
29800	Namely, %cons[x,y]% is the list obtained by putting the  element  %x%
29900	onto the front of the list %y.  Thus
30000	
30100		cons[A,(B C D E)] = (A B C D E).
30200	
30300	If we want %cons[x,y]% to  be  a  list,  then  %y%  must  be  a  list
30400	(possibly the null list %NIL), and %x% must be a list or an atom.  In
30500	the case of S-expressions in general, there is no restriction on  the
30600	arguments  of  %cons.   Usually,  we  shall  write  %x.y%  instead of
30700	%cons[x,y]% since this is briefer.
30800	
30900		The  first  predicate  is  %at%x.   at%x%  is  true  if   the
31000	S-expression %x% is atomic and false otherwise.
31100	
31200		The  second  predicate  is equality of atomic symbols written
31300	%x%eq%y. Equality of S-expressions is tested by a  program  based  on
31400	%eq.   Actually  %eq% does a bit more than testing equality of atoms.
31500	Namely, %x%eq%y% is true if and only if the addresses  of  the  first
31600	words  of  the  S-expressions  %x%  and %y% are equal.  Therefore, if
31700	%x%eq%y, then %x% and y are certainly  the  same  S-expression  since
31800	they  are  represented by the same structure in memory.  The converse
31900	is false because there is no  guarantee  in  general  that  the  same
32000	S-expression is not represented by two different list structures.  In
32100	the particular case where at least one of the S-expressions is  known
32200	to  be  an atom, this guarantee can be given, because LISP represents
32300	atoms uniquely in memory.
32400	
32500		The above are all the basic functions of LISP; all other LISP
32600	functions   can  be  built  from  them  using  recursive  conditional
32700	expressions as will shortly be explained. However, the use of certain
32800	abbreviations makes LISP programs easier to write and understand.
32900	
33000		n%x%  is  an  abbreviation for %x%eq%NIL.  It rates a special
33100	notation because %NIL% plays the same  role  among  lists  that  zero
33200	plays  among  numbers,  and list variables often have to be tested to
33300	see if their value is %NIL.
33400	
33500		The notation  %list[x1,x2,...,xn]%  is  used  to  denote  the
33600	composition of cons's that forms a list from its elements.  Thus
33700	
33800		list[x,y,z] = cons[x,cons[y,cons[z,NIL]]]
33900	
34000	and forms a list of three elements out of the quantities %x, %y,  and
34100	%z.  We  often  write %(x%y%...%z)% instead of %list[x,y,...,z]% when
34200	this will not cause  confusion.   The  presence  of  the  lower  case
34300	letters  is  an  indication  that a function that forms a list rather
34400	than a specific list is meant.
34500	
34600		Compositions of %a% and %d% are written by concatenating  the
34700	letters  %a% and %d.  Thus, it is easily seen that %ad%x% denotes the
34800	second element of the list %x, and %add%x% denotes the third  element
34900	of that list.
35000	
35100	6. Conditional expressions.
35200	
35300		When the form that represents a function depends on whether a
35400	certain  predicate is true of the arguments, conditional expressions.
35500	are used.  The conditional expression
35600	
35700		if p then a else b
35800	
35900	is evaluated as follows:  First %p% is evaluated and determined to be
36000	true or false.  If %p% is true, then %a% is evaluated and  its  value
36100	is  the  value  of  the  expression.   If  %p%  is false, then %b% is
36200	evaluated and its value is the value of the expression.  Note that if
36300	%p% is true, %b% is never evaluated, and if %p% is false, then %a% is
36400	never evaluated.  The importance of this will be explained  later.  A
36500	familiar  function that can be written conveniently using conditional
36600	expressions is the absolute value of a real number.  We have
36700	
36800		|x| = if x<0 then -x else x.
36900	
37000	A more general form of conditional expression is
37100	
37200		if p then a else if q then b ... else if s then d else e.
37300	
37400	There  can  be  any  number  of  terms;  the  value  is determined by
37500	evaluating the propositional terms %p, %q, etc. until a true term  is
37600	found;  the value is then that of the term following the next "then".
37700	If none of the propositional terms is true, then the value is that of
37800	the term following the "else".
37900	
38000		The function graphed in figure 4 is described by the equation
38100	
38200		tri[x] = if x<-1 then 0 else if x<0 then 1+x 
38300	else if x<1 then 1-x else 0.
38400	
38500	
38600	
38700	
38800	
38900	
39000	
39100	
39200	
39300	
39400	                              Figure 4.
39500	
39600	
39700	7. Boolean expressions.
39800	
39900		In  making  up  the  propositional   parts   of   conditional
40000	expressions,   it   is   often   necessary   to   combine  elementary
40100	propositional expressions using the Boolean operators  and,  or,  and
40200	not.   We  use  the  symbols  %∧, %∨, and %¬% respectively, for these
40300	operators.  In LISP, the atoms %T% and %NIL% are used for  the  truth
40400	values.  The Boolean operators may be described simply by listing the
40500	values of the elementary Boolean expressions for  each  case  of  the
40600	arguments.  Thus we have:
40700	
40800		T∧T = T
40900		T∧F = F
41000		F∧T = F
41100		F∧F = F
41200	
41300		T∨T = T
41400		T∨F = T
41500		F∨T = T
41600		F∨F = F
41700	
41800		¬T = F
41900		¬F = T.
42000	
42100		The  Boolean  operators  can  be  described  by   conditional
42200	expressions in the following way:
42300	
42400		p∧q = if p then q else F
42500		p∨q = if p then T else q
42600		¬p = if p then F else T.
42700	
42800	Note that if %p% is false %p∧q% is false independent of the value  of
42900	%q,  and  likewise  if %p% is true, then %p∨q% is true independent of
43000	%q.  If %p% has been evaluated and found to be false, then  %q%  does
43100	not  have  to  be evaluated at all to find the value of %p∧q, and, in
43200	fact, LISP does not evaluate %q% in this case.  Similarly, %q% is not
43300	evaluated  in  evaluating  %p∨q% if %p% is true. This procedure is in
43400	accordance with the above conditional expression descriptions of  the
43500	Boolean operators.  The importance of this convention which contrasts
43600	with that of ALGOL  60,  will  be  apparent  later  when  we  discuss
43700	recursive definitions of functions and predicates.
43800	
43900	8. Recursive function definitions.
44000	
44100		In such languages as FORTRAN and  Algol,  computer  progrrams
44200	are  expressed  in the main as sequences of assignment statements and
44300	conditional go to's.  In LISP, programs are mainly expressed  in  the
44400	form of recursively defined functions.  We begin with an example.
44500	
44600		The  function  %alt[x]%  gives  a  list  whose  elements  are
44700	alternate elements of the list %x% beginning with the first.  Thus
44800	
44900		alt[(A B C D E)] = (A C E),
45000	
45100		alt[(((A B) (C D))] = ((A B)),
45200	
45300		alt[(A)] = (A),
45400	and
45500		alt[NIL] = NIL.
45600	
45700		The function %alt% is defined by the equation
45800	
45900		alt[x] ← if n x ∨ n d x then x else a x . alt[dd x].
46000	
46100		The  above  definition  is  best  explained  by  using  it to
46200	evaluate some expressions.  We start with %alt[NIL]. To evaluate this
46300	expression  we  evaluate  the expression to the right of the %←% sign
46400	remembering that the variable %x% has the value %NIL.  A  conditional
46500	expression  is  evaluated by first evaluating the first propositional
46600	term - in this case %nx%∨%n%d%x. This expression is a disjunction and
46700	in  its evaluation we first evaluate the first disjunct, namely %n%x.
46800	Since %x%=%NIL, %n%x% is true, the disjunction is true, and the value
46900	of  the  conditional  expression  is  the value of the term after the
47000	first true propositiional term. The term is  %x,  and  its  value  is
47100	%NIL,  so the value of %alt[NIL]% is %NIL% as stated above.   Obeying
47200	the rules about the order of evaluation of terms in  conditional  and
47300	Boolean expressions is important in this case since if we didn't obey
47400	these rules, we might find ourselves trying to  evaluate  %n%d%x%  or
47500	%alt[dd%x],  and since %x% is %NIL, neither of these has a value.  An
47600	attempt to evaluate them in LISP would give rise to an error return.
47700	
47800		As a second example, consider  %alt[(A  B)].   Since  neither
47900	%n%x%  nor %n%d%x% is true in this case, the disjunction %n%x%∨%n%dx%
48000	is  false  and  the  value  of  the  expression  is  the   value   of
48100	%a%x%.%alt[dd%x].   a%x%  has  the value %A, and %dd%x% has the value
48200	%NIL, so we must now evaluate %alt[NIL], and we already know that the
48300	value   of   this   expression  is  %NIL.  Therefore,  the  value  of
48400	%alt[(A%B)]% is that of %A.NIL% which is %(A).
48500	
48600		We can describe this  evaluation  in  a  less  wordy  way  by
48700	writing
48800	
48900		alt[(A B)] = if n(A B) ∨ nd(A B) then (A B) else
49000				a(A B).alt[dd(A B)]
49100	
49200			%%%= if NIL ∨ n%d(A B) then (A B) else
49300				a(A B).alt[dd(A B)]
49400	
49500			%%%= if NIL then (A B) else
49600				a(A B).alt[dd(A B)]
49700	
49800			%%%= a(A B).alt[dd(A B)]
49900	
50000			%%%= A.alt[NIL]
50100	
50200			%%%= A.[if nNIL ∨ ndNIL then NIL else
50300				aNIL.alt[ddNIL]]
50400	
50500			%%%= A.[if T ∨ ndNIL then NIL else
50600				aNIL.alt[ddNIL]]
50700	
50800			%%%= A.[if T then NIL else
50900				aNIL.alt[ddNIL]]
51000	
51100			%%%= A.[NIL]
51200	
51300			%%%= (A).
51400	
51500		This is still very  long-winded,  and  now  that  the  reader
51600	understands  the  order  of  evaluation  of  conditional  and Boolean
51700	expressions, we can proceed more briefly to evaluate
51800	
51900		alt[A B C D E)] = A.alt[(C D E)]
52000	
52100				= A.[C.alt[(E)]]
52200	
52300				= A.[C.(E)]
52400	
52500				= (A C E).
52600		Here are three more examples of recursive functions and their
52700	application: We define %last% by
52800	
52900		last[x] ← if n d x then a x else last[d x],
53000	
53100	and we compute
53200	
53300		last[(A B C)] = if nd(A B C) then a(A B C) else last[d(A B C)]
53400	
53500			%%%%%%= last[(B C)]
53600	
53700			%%%%%%= last[(C)]
53800	
53900			%%%%%%= C.
54000	
54100	Clearly  %last%  computes  the  last element of a list.  last[NIL] is
54200	undefined in the LISP language; the result of trying  to  compute  it
54300	may be an error message or may be some random result depending on the
54400	implementation.
54500	
54600		The function %subst% is defined by
54700	
54800		subst[x,y,z] ← if at z then [if z eq y then x else z]
54900				else subst[x,y,a z].subst[x,y,d z].
55000	
55100	We have
55200	
55300		subst[(A.B),X,((X.A).X)] = 
55400	
55500			= subst[(A.B),X,(X.A)].subst[(A.B),X,X]
55600	
55700			= [subst[(A.B),X,X].subst[(A.B),X,A]].(A.B)
55800	
55900			= [[(A.B)].A].(A.B)]
56000	
56100			= (((A.B).A).(A.B)).
56200	
56300	subst% computes the result of substituting the S-expression  %x%  for
56400	the  atom %y% in the S-expression %z.  This is an important operation
56500	in all kinds of symbolic computation.
56600	
56700		Another important operation is the  concatenation  of  lists,
56800	and  it is generally denoted by the infixed expression %x*y% since it
56900	is associative.  We have the examples
57000	
57100		(A B C)*(D E F) = (A B C D E F),
57200	
57300	and
57400	
57500		NIL*(A B) = (A B) = (A B)*NIL,
57600	
57700	and the formal definition
57800	
57900		x*y ← if n x then y else [a x].[[d x]*y].
58000	
58100		The  Boolean  operations can also be used in making recursive
58200	definitions  provided  we  observe  the  order   of   evaluation   of
58300	constituents. First, we define a predicate %equal% by
58400	
58500		equal[x,y] ← x eq y ∨ [¬at x ∧ ¬at y ∧
58600				equal[a x,a y] ∧ equal[d x,d y]].
58700	
58800	equal[x,y]% is true  if  and  only  if  %x%  and  %y%  are  the  same
58900	S-expression,  and  the  use  of this predicate makes up for the fact
59000	that the basic predicate %eq% is guaranteed  to  test  equality  only
59100	when  one  of the operands is known to be an atom.  We shall also use
59200	the infixes %=% and %≠.
59300	
59400		Membership of an S-expression %x% in a list %y% is tested by
59500	
59600		member[x,y] ← ¬n y ∧ [[x = a y] ∨ member[x,d y]].
59700	
59800	This relation is also denoted by %xεy.  Here are some computations:
59900	
60000		member[B,(A B)] = ¬n (A B) ∧ [[B = a (A B)] 
60100				%%%%∨ member[B,d (A B)]],
60200	
60300				= member[B,(B)]
60400	
60500				= T.
60600	
60700		Sometimes  a  function  is defined with the help of auxiliary
60800	functions.  Thus, the reverse of a list %x%, (e.g.  %reverse[(A  B  C
60900	D)] = (D C B A)), is given by
61000	
61100		reverse[x] ← rev[x,NIL]
61200	
61300	where
61400	
61500		rev[x,y]   ← if n x then y else rev[d x,[a x].y].
61600	
61700	A computation is
61800	
61900		reverse[(A B C)] = rev[(A B C),NIL]
62000	
62100				%= rev[(B C),(A)]
62200	
62300				%= rev[(C),(B A)]
62400	
62500				%= rev[NIL,(C B A)]
62600	
62700				%= (C B A).
62800	
62900		A more elaborate example of recursive definition is given by
63000	
63100		flatten[x] ← flat[x,NIL]
63200	
63300		flat[x,y]  ← if at x then x.y else flat[a x, flat[d x,y]].
63400	
63500	We have
63600	
63700		flatten[((A.B).C)] = flat[((A.B).C),NIL]
63800	
63900				%%%= flat[(A.B),flat[C,NIL]]
64000	
64100				%%%= flat[(A.B),(C)]
64200	
64300				%%%= flat[A,flat[B,(C)]]
64400	
64500				%%%= flat[A,(B C)]
64600	
64700				%%%= (A B C).
64800	
64900	The  reader  will see that the value of %flatten[x]% is a list of the
65000	atoms  of  the  S-expression  %x%   from   left   to   write.    Thus
65100	%flatten[((A%B)%A)]%=%(A%B%NIL%A%NIL).
65200	
65300		Many  functions  can be conveniently written in more than one
65400	way.  For example, the function  %reverse%  mentioned  above  can  be
65500	written without an auxiliary function as follows:
65600	
65700		reverse[x] ← if n x then NIL else reverse[d x]*(a x)
65800	
65900	but it will be explained later that the earlier  definition  involves
66000	less computation.
66100	
66200		The use of conditional  expressions  for  recursive  function
66300	definition  is  not  limited  to  functions  of  S-expressions.   For
66400	example, the factorial function and the Euclidean algorithm  for  the
66500	greatest common divisor are expressed as follows:
66600	
66700		n! ← if n=0 then 1 else n.(n-1)!
66800	
66900	and
67000	
67100		gcd(m,n) ← if m>n then gcd(n,m) else if m=0 then n
67200				else gcd(n mod m,m)
67300	
67400	where %n mod m% denotes the remainder when %n% is divided by %m%  and
67500	may itself be expressed recursively by
67600	
67700		n mod m ← if n<m then n else (n-m) mod m.
67800	
67900	
68000	                              Exercises
68100	
68200		1. Consider the function %drop% defined by
68300	
68400		drop[x] ← if n x then NIL else (a x).drop[d x].
68500	
68600	Compute (by hand) %drop[(A B C)].  What does %drop% do  to  lists  in
68700	general?
68800	
68900		2. What does the function
69000	
69100		r2[x] ← if n x then NIL else reverse[a x].r2[d x]
69200	
69300	do to lists of lists?  How about
69400	
69500		r3[x] ← if at x then x else reverse[r4[x]]
69600	
69700		r4[x] ← if n x then NIL else r3[a x].r4[d x]?
69800	
69900		3. Compare
70000	
70100		r3'[x] ← if at x then x else r3'[d x]*(r3'[a x])
70200	
70300	with the function %r3% of the preceding example.
70400	
70500		4. Consider %r5% defined by
70600	
70700		r5[x] ← if n x ∨ n d x then x
70800			else [a r5[d x]] . r5[a x . r5[d r5[d x]]].
70900	
71000	Compute %r5[(A B C D)].  What does %r5% do in general.   Needless  to
71100	say, this is not a good way of computing this function even though it
71200	involves no auxiliary functions.
71300	
71400	
71500	9. Lambda expressions and functions with functions as arguments.
71600	
71700		It is common to use phrases like "the function %2x+y".   This
71800	is  not a precise notation because we cannot say %2x+y(3,4)% and know
71900	whether the desired  result  is  %2.3+4%  or  %2.4+3%  regarding  the
72000	expression  as a function of two variables.  Worse yet, we might have
72100	meant a one-variable function of %x% wherein %y%  is  regarded  as  a
72200	parameter.
72300	
72400		The problem  of  giving  names  to  functions  is  solved  by
72500	Church's   λ-notation.    In   the  above  example,  we  would  write
72600	%λx%y.2x+y% to denote  the  function  of  two  variables  with  first
72700	argument  %x%  and  second  argument  %y% whose value is given by the
72800	expression %2x+y.  Thus,
72900	
73000		[λx y.2x+y][3,4] = 10.
73100	
73200	Likewise,  %[λy%x.2x+y][3,4]%=%11.  Like variables of integration and
73300	the bound variables of quantifiers in logic, variables following  %λ%
73400	are  bound  or dummy and the expression as a whole may be replaced by
73500	any others provided the replacement is done consistently and does not
73600	make  any  variable  bound  by %λ% the same as a free variable in the
73700	expression.  Thus  %λx%y.2x+y%  represents  the  same   function   as
73800	%λy%x.2y+x%  or  %λu%v.2u+v%,  but  in  the  function of one argument
73900	%λx.2x+y%, we cannot replace the variable %x% by %y%, though we could
74000	replace it by %u.
74100	
74200		λ-notation plays two important  roles  in  LISP.   First,  it
74300	allows us to rewrite an expression containing two or more occurrences
74400	of the same sub-expression in such a way that the  expression  occurs
74500	only    once.     Thus    %(2x+1)↑4+3(2x+1)↑3%    can    be   written
74600	%[λw.w↑4+3w↑3][2x+1].  This can save  considerable  computation,  and
74700	corresponds to the practice in ordinary programming of assigning to a
74800	variable the value of a sub-expression that occurs more than once  in
74900	an  expression  and  then  writing  the  expression  in  terms of the
75000	variable.
75100	
75200		The second use of λ-expressions is in  using  functions  that
75300	take functions as arguments.  Suppose we want to form a new list from
75400	an old one by applying a function %f% to each element  of  the  list.
75500	This can be done using the function %mapcar% defined by
75600	
75700		mapcar[x,f] ← if n x then NIL else f[a x].mapcar[d x,f].
75800	
75900	Suppose the operation we want to perform is squaring, and we want  to
76000	apply it to the list %(1 2 3 4 5 6 7).  We have
76100	
76200		mapcar[(1 2 3 4 5 6 7),λx.x↑2] = (1 4 9 16 25 36 49).
76300	
76400		A more generally useful operation than %mapcar% is  %maplist%
76500	in  which  the  function is applied to the successive sublists of the
76600	list rather than to the elements.  maplist% is defined by
76700	
76800		maplist[x,f] ← if n x then NIL else f[x].maplist[d x,f].
76900	
77000		As  an  application  of %maplist and functional arguments, we
77100	shall define a function  for  differentiating  algebraic  expressions
77200	involving sums and products.  The expressions are built up from atoms
77300	denoting variables and integer constants according to the syntax
77400	
77500		<expression> ::= <variable>|<integer>|
77600				%(PLUS <explist>)|(TIMES <explist>)
77700	
77800		<explist>    ::= <expression>|<expression><explist>
77900	
78000	Here, %PLUS% followed by a list of arguments denotes the sum of these
78100	arguments and %TIMES% followed by a list of arguments  denotes  their
78200	product.   The  function  %diff[e,v]% gives the partial derivative of
78300	the expression %e% with respect to the variable %v. We have
78400	
78500		diff[e,v] ← if at e then [if e eq v then 1 else 0]
78600			else if a e eq PLUS then
78700				PLUS.mapcar[d e,λx.diff[x,v]_]
78800			else if a e eq TIMES then
78900				PLUS.maplist[d e,λx.TIMES.
79000					maplist[d e,λy.if x eq y then
79100						diff[a y,v] else a y]].
79200	
79300	The  term  that  describes  the  rule  for  differentiating  products
79400	corresponds to the rule
79500	
79600		∂/∂v[   e[i] =        [if i=j then ∂e[j]/∂v else e[j]].
79700	
79800	and  %maplist%  has  to be used rather than %mapcar% since whether to
79900	differentiate in forming the product is determined by equality of the
80000	indices  %i%  and  %j%  rather  than equality of the terms %e[i]% and
80100	%e[j].
80200	
80300		Two more useful functions with functions as arguments are the
80400	predicates %andlis% and %orlis% defined by the equations
80500	
80600		andlis[u,p] ← n u ∨ [p[a u] ∧ andlis[d u,p]]
80700	
80800	and
80900	
81000		orlis[u,p] ← ¬n u ∧ [p[a u] ∨ orlis[d u,p]].
81100	
81200	
81300	                              Exercises
81400	
81500		1. Compute %diff[(TIMES X (PLUS Y 1) 3),X]% using  the  above
81600	definition  of %diff.  Now do you see why algebraic simplification is
81700	important?
81800	
81900		2. Compute %orlis[((A B) (C D) E),at].
82000	
82100	
82200	10. Label.
82300	
82400		The λ mechanism is  not  adequate  for  providing  names  for
82500	recursive  functions,  because  in this case there has to be a way of
82600	referring to the function name within the  function.   Therefore,  we
82700	use  the notation %label[f,e]% to denote the expression %e% but where
82800	occurrences of %f% within %e% refer  to  the  whole  expression.  For
82900	example,  suppose we wished to define a function that takes alternate
83000	elements of each element of a list and makes a list of these.   Thus,
83100	we want
83200	
83300		glub[((A B C) (A B C D) (X Y Z))] = ((A C) (A C) (X Z)).
83400	
83500	We can make the definition
83600	
83700		glub[x] ← mapcar[x,label[alt,λx.if n x ∨ n d x then x
83800						else a x . alt[dd x]]].
83900	
84000	The identifier %alt% in the above example is bound by the %label% and
84100	is  local  to  that  expression,  and  this is the general rule.  The
84200	%label% construction is not often used in LISP since it is more usual
84300	to  give functions global definitions. D. M. R. Park pointed out that
84400	if we allow variables to represent functions and use a  suitable  %λ%
84500	construction, the use of %label% could be avoided.